/**
 * 
 * @param {待排序数组} arr 
 */
// 第一个元素已经有序，从第二个元素出发，和前面的相比，找到合适的位置插入即可
// 时间n^2 空间1
function insertionSort(arr) {
  for(let i = 1; i < arr.length; i++) {
    let j = i - 1
    let key = arr[i]
    while(j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j]
      j--
    }
    arr[j + 1] = key
  }
  return arr
}
let arr = [3, 12, 2, 9, 0, 88]
console.log(insertionSort(arr));